COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00009 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\def\ld{\mathrel{\hbox{$<$\kern-4pt$\cdot$}}}
\def\gd{\mathrel{\hbox{$\cdot$\kern-4pt$>$}}}
\rm
\line{\sevenrm a05.tex[257,phy] \today\hfill}

\bigskip
\noindent
{\bf Complexity of Polynomial Root-finding.}

\bigskip
Let $p↓n(x)$ be a polynomial of degree $n≥2$, with integer coefficients,
and irreducible over the rationals.
Since $p'↓n(x)$ has degree $n-1≥1$, and multiple roots of~$p↓n$ are
roots of~$p'↓n$, $p↓n(x)$ has
no multiple roots, and $p'↓n(x)$ is bounded away from zero in a neighborhood
of every root of~$p↓n(x)$. How many steps of rational arithmetic are
needed to find an approximate root~$r=a/b$ for which $\left|p↓n(r)\right|≤\epsilon$?
Since  $p↓n(r)≠0$ (otherwise $p↓n(x)$ is divisible by $x-r$),
$\epsilon ≥\left|p↓n(r)\right|≥b↑{-n}$, or $b≥\epsilon↑{-1/n}$.

If the computation uses rational constants with numerators and denominators
bounded by~$c$, an easy induction shows that after $i$~steps of rational
operations (even allowing unlimited parallelism), all numerators and
denominators  of the computed numbers
(including~$b$) are bounded by $(2c)↑{2↑i}/2$. Then we find
$\epsilon↑{-1/n}≤b≤(2c)↑{2↑i}/2$. Solving for~$i$,
$$\eqalignno{i&≥\lg(1-\lg\epsilon/n)-\lg(1+\lg c)\,.&(1)\cr
\noalign{\medskip}
i&≥\lg\lg (1/\epsilon)+\lg\lg c+O(1)\,.\cr}$$
If we want $r$ correct to $b$~bits (more precisely, we want 
$\left|p↓n(x)\right|≤2↑{-b}$),
we must have $-\lg\epsilon ≥b$, so
$$i≥\lg b-\lg n-k\,,$$
where the constant $k$ represents the time saved by precomputing the constants
in the algorithm.

For example, suppose we compute $\sqrt{2}$, using (as does Newton's method)
constants with numerator and denominator $≤2$, so $k=1$, $n=2$. Then
$i≥\lg b-2$. Since Newton's method takes time $O(\lg b)$, it is within
a (small) constant factor of being as fast as possible.

\bigskip\noindent
Error analysis -- Newton's method for $\sqrt{y}$.

Define
$$\displaylines{r↓{i+1}={r↓i+y/r↓i\over 2}\cr
\noalign{\smallskip}
\hbox{($r↓i$ is the $i↑{\rm th}$ approximation to $\sqrt{y}\;$)}\cr
\noalign{\smallskip}
t↓i={r↓i\over \sqrt{y}}-1\,,\quad r↓i=(t↓i+1)\sqrt{y}\,;\cr
\noalign{\smallskip}
\hbox{($t↓i$ is the relative error in $r↓i$ as an approximation to $\sqrt{y}\;$)}\cr
\noalign{\smallskip}
w↓i={1\over t↓i}+{1\over 2}\,,\quad t↓i={2\over w↓i-1}\,.\cr}$$
Then
$$\eqalign{w↓i&={2\over t↓i}+1
={r↓i+\sqrt{y}\over r↓i-\sqrt{y}}\,,\quad w↓0={r↓0+\sqrt{y}\over r↓0-\sqrt{y}}\cr
\noalign{\smallskip}
w↓{i+1}&={r↓{i+1}+\sqrt{y}\over r↓{i+1}-\sqrt{y}}={r↓i+2\sqrt{y}+y/r↓i\over
r↓i-2\sqrt{y}+y/r↓i}=w↓i↑2\,,\cr}$$
so by induction
$$w↓i=\left(\,{r↓0+\sqrt{y}\over r↓0-\sqrt{y}}\,\right)↑{2↑i}\,.$$
Back-substituting,
$$r↓i=(t↓i+1)\sqrt{y}=\left(\,{2\over w↓i-1}+1\right)
\sqrt{y}={w↓i+1\over w↓i-1}\sqrt{y}
=\sqrt{y}{(r↓0+\sqrt{y}\,)↑{2↑i}+(r↓0-\sqrt{y}\,)↑{2↑i}\over 
(r↓0+\sqrt{y}\,)↑{2↑i}-(r↓0-\sqrt{y}\,)↑{2↑i}}\,.$$
A similar closed form for $t↓i$, the relative error after $i$~steps, is
$$t↓i={2\over w↓i-1}=
{2\over \left(\,{r↓0+\sqrt{y}\over r↓0-\sqrt{y}}\,\right)↑{2↑i}-1}\,.$$
For large $i$, the $-1$ in the denominator can be ignored, and the relative
error is $t↓i\approx
2\left(\,{r↓0-\sqrt{y}\over r↓0+\sqrt{y}}\,\right)↑{2↑i}$.
Solving for $i$ as a function of the relative error~$t↓i$, 
$$i=\lg\lg\left({2\over t↓i}+1\right)-\lg\lg\left({2\over t↓0}+1\right)\,.\eqno(2)$$
For example, if $n=2$ and
the desired $t↓i$ is $2↑{-32}$, the lower bound given by~(1) is
$$i≥\lg\left(1-{\lg(2↑{-32})\over 2}\right)-\lg(1+\lg 2)=3.09\,;$$
since $i$ is an integer, $i≥4$. An upper bound from~(2)
is, (for $t↓0=1$), $i=\lceil 4.38\rceil =5$.


\bigskip
\parindent0pt
\copyright 1985 Robert W. Floyd

First draft (not published) February 11, 1985.

\bye